package cn.tedu.numbersum;

import java.util.*;

/**
 * 给定一个整形数组，再给定一个数字，判断能否在这个数组中找到一个或几个数字，使得它们的和等于指定的数字
 * 比如: 3, 34, 4, 12 ,5, 2
 * 能否凑出12
 */
public class SumTheNumberFromNumbers {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int count = input.nextInt();
        int[] arr = new int[count];
        for (int i = 0; i < count; i++) {
            arr[i] = input.nextInt();
        }
        int target = input.nextInt();
        System.out.println(dpCalc(arr, arr.length - 1, target));
    }

    private static boolean recCalc(int[] arr, int index, int total) {
        if (total == 0)
            return true;
        if (index == 0)
            return arr[index] == total;
        if (arr[index] > total)
            return recCalc(arr, index - 1, total);
        else {
            boolean hasSelf = recCalc(arr, index - 1, total - arr[index]);
            boolean noSelf = recCalc(arr, index - 1, total);
            return hasSelf || noSelf;
        }
    }

    private static boolean dpCalc(int[] arr, int index, int total) {
        boolean[][] rw = new boolean[index + 1][total + 1];
        int row = index + 1;
        int col = total + 1;
        Arrays.fill(rw[0], false);
        rw[0][arr[0]] = true;
        for (int i = 0; i < rw.length; i++) {
            rw[i][0] = true;
        }
        for (int i = 1; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (arr[i] > j)
                    rw[i][j] = rw[i - 1][j];
                else {
                    boolean hasSelf = rw[i - 1][j - arr[i]];
                    boolean noSelf = rw[i - 1][j];
                    rw[i][j] = hasSelf || noSelf;
                }
            }
        }

        return rw[row - 1][col - 1];
    }
}
